#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : SumLeftLeaves.py
# @Time    : 2020/9/19 13:58
# @Description:


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        """
        Find the sum of all left leaves in a given binary tree.

        Example:

                3
               / \
              9  20
                /  \
               15   7

        There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

        :param root:
        :return:
        """
        queue = [root]
        ans = 0
        while len(queue):
            node = queue.pop(0)
            if node:
                if node.left:
                    if not node.left.left and not node.left.right:
                        ans += node.left.val
                    else:
                        queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

    def sumOfLeftLeaves2(self, root: TreeNode) -> int:
        isLeafNode = lambda node: not node.left and not node.right

        def helper(node: TreeNode):
            ans = 0
            if node.left:
                ans += node.left.val if isLeafNode(node.left) else helper(node.left)
            if node.right:
                ans += helper(node.right)
            return ans

        return helper(root) if root else 0


if __name__ == '__main__':
    S = Solution()
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(S.sumOfLeftLeaves(root))
    print('done')
